package me.timlong.dp;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

public class MinPathLength {


    /*
    可以发现一个规律：第l个数组的第k个元素的下一个元素的有两种可能，
    分别是第l+1个数组的第k个元素与第k+1个元素。所以递归取最小值搞定
    */

    /**
     *
     * 整个三角形可以看做一个二叉树，用f表示二叉树深度，从1到n。
     * 二维ArrayList<ArrayList<Integer>> 可以看做是一个一维数组，其中index表示数组的游标，从0到len-1。
     * 左孩子就是当前节点加上这层孩子的数目f，也就是index+f
     * len是一维数组，也可以用来约束一维数组的index是否越界，换句话，就是可以判断叶子节点。
     *
     */

    public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
        int sum ;
        sum = getResult(triangle,0,0);
        return sum;
    }

    public int getResult(ArrayList<ArrayList<Integer>> triangle, int l, int k) {
        int sum = triangle.get(l).get(k);
        if(l<triangle.size()-1)
            sum += Math.min(getResult(triangle,l+1,k),getResult(triangle,l+1,k+1));
        return sum;
    }


    /**
     *  DP，复用一个长度triangle.size()大小的数组记录
     *  上一层元素的构成的小三角的最小路径和,状态转移方程
     *  f(i,j) = min(f(i+1, j) + triangle[i][j], f(i+1, j+1) + triangle[i][j])
     */
    public int minimumTotal_plus(ArrayList<ArrayList<Integer>> triangle) {
        if(triangle.size()<1) return 0;
        int[] min = new int[triangle.size()];
        for(int i=0; i<triangle.size(); i++){
            min[i] = triangle.get(triangle.size()-1).get(i);
        }
        for(int i=triangle.size()-2; i>=0; i--){
            for(int j=0; j<=i; j++){
                min[j] = Math.min(min[j]+triangle.get(i).get(j),
                        min[j+1]+triangle.get(i).get(j));
            }
        }
        return min[0];
    }


    /**
     * 给出一个三角形，计算从三角形顶部到底部的最小路径和，每一步都可以移动到下面一行相邻的数字，
     * 例如，给出的三角形如下：
     *      [2],↵
     *     [3,4],↵
     *    [6,5,7],↵
     *   [4,1,8,3]↵
     * 最小的从顶部到底部的路径和是2 + 3 + 5 + 1 = 11。
     * 注意：
     * 如果你能只用O（N）的额外的空间来完成这项工作的话，就可以得到附加分，其中N是三角形中的行总数。
     *
     *  解决方案：
     *  思路：自底向上进行列加
     *
     *  递推公式： f(i, j) -> 表示以第i行第j个元素为root，到最底层的累加路径最小值
     *
     *  定义二维数组 dp[i][j] 表示f(i, j)，但是题目要求空间O（n）,考虑到自底向上，在上一层dp数组被
     *  使用之后，在上一层的dp计算就不再使用，故可以考虑重用一位数组
     */



    public int myTriangleTotal_min(ArrayList<ArrayList<Integer>> triangle){
        int height = triangle.size();


        // 最底层的元素个数与height相同
        int[] min = new int[height];

        for (int i = 0; i < height; i++)
            min[i] =  triangle.get(height - 1).get(i);

        for (int i = height - 2 ; i >= 0 ; i--) {
            for (int j = 0; j < triangle.get(i).size(); j++) {
                min[j] = Math.min(min[j] + triangle.get(i).get(j), min[j + 1] + triangle.get(i).get(j));
            }
        }
        return min[0];
    }




    public static void main(String[] args) {

        Integer[] arr1 =     {2};
        Integer[] arr2 =    {3,4};
        Integer[] arr3 =   {6,5,7};
        Integer[] arr4 =  {4,1,8,3};

        ArrayList<Integer> lev1 = new ArrayList<Integer>(Arrays.asList(arr1));
        ArrayList<Integer> lev2 = new ArrayList<>(Arrays.asList(arr2));
        ArrayList<Integer> lev3 = new ArrayList<>(Arrays.asList(arr3));
        ArrayList<Integer> lev4 = new ArrayList<>(Arrays.asList(arr4));
        ArrayList<ArrayList<Integer>> arrayLists = new ArrayList<>();
        arrayLists.add(lev1);
        arrayLists.add(lev2);
        arrayLists.add(lev3);
        arrayLists.add(lev4);

        System.out.println(new MinPathLength().myTriangleTotal_min(arrayLists));


    }
}
